---
title: "迷宫问题"
created: 2025-11-28
tags:
  - 算法
---

# 迷宫问题

## 题目 [迷宫问题](https://www.cnblogs.com/littlehb/p/15955249.html)

给定一个 n×n 的二维数组，如下所示：

```cpp
int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};
```

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

数据保证至少存在一条从左上角走到右下角的路径。

**输入格式**

第一行包含整数 n。

接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。

**输出格式** 输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。

按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。

**数据范围**

0≤n≤1000

**输入样例**：

```text
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
```

**输出样例**：

```text
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
```

## 思路分析

模版基础上加个p[] 与4个拓展坐标一一对应

达到终点的时候 做一次dfs回溯路径

pre记录的是这个点被上个点往哪个方向转移而来

所以从当前点找回上一个点 应该与URDL逻辑相反

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=1010;

int g[N][N],d[N][N];

char pre[N][N];

int n;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

char p[4]={'U','R','D','L'};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=n-1 && d[x][y]==-1;

}

void print_path(int x,int y){

	if(x<0 || y<0)	return;

	if(pre[x][y]=='U')

		print_path(x+1,y);

	if(pre[x][y]=='R')

		print_path(x,y-1);

	if(pre[x][y]=='D')

		print_path(x-1,y);

	if(pre[x][y]=='L')

		print_path(x,y+1);

	cout<<x<<" "<<y<<endl;

}

void bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	q.push({x,y});

	d[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		if(ux==n-1 && uy==n-1){

			print_path(ux,uy);

			return;

		}

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]==0){

				q.push({nx,ny});

				d[nx][ny]=d[ux][uy]+1;

				pre[nx][ny]=p[i];

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	for(int i=0;i<n;i++){

		for(int j=0;j<n;j++){

			cin>>g[i][j];

		}

	}

	bfs(0,0);

	return 0;

 }
```

## 同类题型

## 视频讲解

---
⬅️ [[走迷宫|走迷宫]] 🏠 [[00-刷题理模型]] ➡️ [[迷宫问题（最短路）|迷宫问题（最短路）]]